#include "linearList.h"
#include<iostream>
using namespace std; 
//                顺序表
//初始化顺序表
sequenceList::sequenceList(const int& maxCap, const int& initSize, float initArray[])
{
    maxCapcity = maxCap;
    curNumberOfItem = initSize;
    myList = new float[maxCapcity];

    for (int i=0;i<initSize;i++)
    {
        myList[i] = initArray[i];
    }

}

//销毁顺序表
sequenceList::~sequenceList()
{
    delete[] myList;
}

//添加元素顺序表尾
bool sequenceList::addItem(const float& item)
{
    if(curNumberOfItem>=maxCapcity)
        return false;
    myList[curNumberOfItem] = item;
    curNumberOfItem++;
    return true;
}

//插入元素
bool sequenceList::insertItem(const int& index,const float& item)
{
    if(index<0||index>curNumberOfItem||curNumberOfItem>=maxCapcity)
        return false;
    for (int i=curNumberOfItem;i>index;i--)
    {
        myList[i]=myList[i-1];
    }
    myList[index]=item;
    curNumberOfItem++;
    return true;
}

//删除元素
int sequenceList::deleteItem(const float& item)
{
    for (int i=0;i<curNumberOfItem;i++)
    {
        if(myList[i]==item)
        {
            for (int j=i;j<curNumberOfItem-1;j++)
            {
                myList[j]=myList[j+1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

//查找元素（按照序号）
bool sequenceList::locate(const int& index,float& val)
{
    if(index < 0 || index>=curNumberOfItem)
        return false;
    val = myList[index];
    return true;
}

//查找元素（按值查找）
int sequenceList::locate(const float& item)
{
    for (int i=0;i<curNumberOfItem;i++)
    {
        if(myList[i]==item)
            return i;
    }
    return -1;
}

//倒序排列元素
void sequenceList::reverse()
{
    for (int i=0;i<curNumberOfItem/2;i++)
    {
        float a=myList[i];
        myList[i]=myList[curNumberOfItem-1-i];
        myList[curNumberOfItem-1-i]=a;
    }
}

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

//            链表
//初始化链表
listNode::listNode(float nodedata,listNode* succ)
{
    data=nodedata;
    next=succ;
}
listNode::~listNode()
{

}
linkList::linkList()
{
    firstNode=new listNode();
    lastNode=firstNode;
    curNode=firstNode;
    listSize=0;
}
linkList::linkList(const int& initSize,float initArray[])
{
    firstNode=new listNode();
    lastNode=firstNode;
    curNode=firstNode;
    listSize=0;
    for(int i=0;i<initSize;i++)
    {
        tailInsertItem(initArray[i]);
    }
}

//销毁链表
linkList::~linkList()
{
    curNode=firstNode;
    while(curNode!=NULL)
    {
        listNode* temp=curNode;
        curNode=curNode->next;
        delete temp;
    }
}

//插入元素（头插法）
bool linkList::headInsertItem(const float& item)
{
    listNode* newNode =new listNode(item,firstNode->next);
    firstNode->next=newNode;
    if(lastNode==firstNode)
        lastNode=newNode;
    listSize++;
    return true;
}

//插入元素（尾插法）
bool linkList::tailInsertItem(const float& item)
{
    listNode* newNode = new listNode(item);
    lastNode->next =newNode;
    lastNode=newNode;
    listSize++;
    return true;
}

//指定插入
int linkList::insertItem(const int& index,const float& item)
{
    if(index<0||index>listSize)
        return -1;
    curNode=firstNode;
    for(int i=0;i<index;i++)
    {
        curNode=curNode->next;
    }
    listNode* newNode=new listNode(item,curNode->next);
    curNode->next=newNode;
    if(newNode->next==NULL)
        lastNode=newNode;
    listSize++;
    return index;
}

//删除元素
int linkList::deleteItem(const float& item)
{
    curNode = firstNode;
    int position=0;
    while(curNode->next!=NULL)
    {
        if(curNode->next->data==item)
        {    listNode*temp =curNode->next;
            curNode->next=temp->next;
        if(temp==lastNode)
            lastNode=curNode;
        delete temp;
        listSize--;
        return position;
        }
    curNode=curNode->next;
    position++;
    }
    return -1;
}

//查找元素（按序号找）
bool linkList::locate(const int& index,float& val)
{
    if(index<0||index>=listSize)
        return false;
    curNode=firstNode->next;
    for(int i=0;i<index;i++)
    {
        curNode=curNode->next;
    }
    val=curNode->data;
    return true;
}

//按值查找
int linkList::locate(const float& item)
{
    curNode=firstNode->next;
    int position =0;
    while(curNode!=NULL)
    {
        if(curNode->data==item)
            return position;
        curNode=curNode->next;
        position++;
    }
    return -1;
}

//递增排序
void linkList::ascendingOrder()
{
    if(listSize<=1)return;
    bool swapped;
    do{
        swapped=false;
        curNode=firstNode->next;
        while(curNode->next!=NULL)
        {
            if(curNode->data>curNode->next->data)
            {
                float temp = curNode->data;
                curNode->data=curNode->next->data;
                curNode->next->data=temp;
                swapped=true;
            }
            curNode=curNode->next;
        }
    }while(swapped);
}

//倒序排列元素
void linkList::reverse()
{
    if(listSize<=1)return;
    listNode*prev=NULL;
    listNode*current=firstNode->next;
    listNode*next=NULL;
    lastNode=current;
    while(current!=NULL)
    {
        next=current->next;
        current->next=prev;
        prev=current;
        current=next;
    }
    firstNode->next=prev;
}
//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

//合并链表
void merge(linkList& A, linkList& B) {
    if (B.listSize == 0) return;
    A.lastNode->next = B.firstNode->next;
    A.lastNode = B.lastNode;
    A.listSize += B.listSize; 
    B.firstNode->next = NULL;
    B.lastNode = B.firstNode;
    B.listSize = 0;
    A.ascendingOrder();
    A.reverse();
}
